package Datastruct.BinarySort;

public class BinartSortTree {

    private Node root;

    public Node getRoot() {
        return root;
    }

    //查询
    public Node selectByval(int val) {
        if (root == null) {
            return null;
        } else {
            return root.selectByval(val);
        }
    }

    //查询父结点
    public Node seleByparent(int val) {
        if (root == null) {
            System.out.println(" root  is null");
            return null;
        } else {
            return root.selectByparent(val);
        }
    }

    //添加结点

    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    //中序遍历

    public void inOrder() {
        if (root != null) {
            root.inOrder();
        } else {
            System.out.println("空树。。。");
        }
    }

    /**
     * 删除结点
     * 1.如果删除的结点是叶子结点，找到父结点断开关联
     * 2.如果删除的结点带有左子树或者右子树，把左子树或者右子树的结点交给删除该结点的父结点
     * 3.如果删除的结点带有双亲结点，可以从左子树中找出最大的结点替换删除结点，或者右子树中找出最小的结点替换该结点
     */

    //找出右子树最小值
    public int rightTreeMin(Node node) {
        Node target = node;
        while (target.left != null) {
            target = target.left;
        }
        delNode(target.value);
        return target.value;


    }


    //删除结点
    public void delNode(int val) {
        if (root == null) {
            return;
        } else {
            //删除的目标
            Node target = selectByval(val);
            if (target == null) {
                return;
            }
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            //找到目标结点的父结点
            Node parentnode = seleByparent(val);

            //1.删除的是叶子结点
            if (target.left == null && target.right == null) {
                //判断删除的是左节点还是右节点
                if (parentnode.left != null && parentnode.left.value == val) {
                    //左节点
                    parentnode.left = null;
                } else if (parentnode.right != null && parentnode.right.value == val) {
                    parentnode.right = null;
                }
            } else if (target.left != null && target.right != null) {
                //2.删除的是双亲结点
                int minVal = rightTreeMin(target.right);
                target.value = minVal;

            } else {
                //删除的只有一个子树（可能左子树，可能右子树）
                if (target.left != null) {
                    //左子树
                    if (parentnode != null) {
                        //确定是左子结点
                        if (parentnode.left.value == val) {
                            parentnode.left = target.left;
                        } else {
                            //右子结点
                            parentnode.right = target.left;
                        }
                    } else {
                        root = target.left;
                    }

                } else {//右子树
                    if (parentnode != null) {
                        if (parentnode.left.value == val) {
                            parentnode.left = target.right;
                        } else {
                            parentnode.right = target.right;
                        }
                    } else {
                        root = target.right;
                    }

                }
            }
        }
    }
}
